A related storage system includes NoSQL such as distributed Key-Value Store (KVS). In this storage system, a known technique arranges replicas, which are replications of data, in a plurality of nodes. A storage system with this technique arranges replicas in a plurality of nodes to prevent data loss due to disk failure or the like. The storage system also permits reading out data from the replicas to distribute access load.
Here, the storage system may demand Strong Consistency, which guarantees consistency of data read out from each replica. An exemplary method to maintain Strong Consistency includes a known technique of chain replication. An exemplary storage system with the chain replication will be described below.
First, an exemplary processing will be described by referring to FIG. 21. This processing is executed by the storage system in the case where a client has issued a Put request. FIG. 21 is a block diagram illustrating an exemplary chain replication. FIG. 21 illustrates a storage system with CRAQ (Chain Replication with Apportioned Query) as an exemplary chain replication.
The exemplary storage system in FIG. 21 includes N nodes, which have the same replicas. In FIG. 21, nodes other than a first node, a second node, a third node, and an Nth node among the N nodes are omitted in the exemplary storage system.
Each node in the storage system sequentially forwards an update request, which requests to write data, along a route with the nodes arranged in order in the case where the client has issued the Put request. For example, the exemplary storage system in FIG. 21 specifies the first node, which is a starting end of the route, as an issuance destination of the Put request. In this case, the client issues the Put request to the first node, which is a starting end of the route, as illustrated by (A) in FIG. 21.
The first node prepares to write new data and transmits the update request to the second node in the case where the first node has received the Put request as illustrated by (B) in FIG. 21. The second node prepares to write the new data and forwards the update request to the third node in the case where the second node has received the update request from the first node.
Then, each node sequentially forwards the update request until the Nth node, which is a terminating end of the route, receives the update request. As illustrated by (C) in FIG. 21, the Nth node, which is the terminating end of the route, writes the new data and transmits an updated request, which is a response to the update request, to the node immediately before the Nth node in the case where the Nth node has received the update request.
Then, each node writes prepared data and sequentially forwards the updated request along the route up to the first node, which is the starting end, in the case where the node has received the updated request. Then, the first node writes prepared data and notifies the client of completion of the data writing processing in the case where the first node has received the updated request as illustrated by (D) in FIG. 21.
Non-Patent Literature 1: Object Storage on CRAQ, High-throughput chain replication for read-mostly workloads, Jeff Terrace and Michael J. Freedman Princeton University, USENIX annual Technical Conference. San Diego, Calif., June 2009.
Non-Patent Literature 2: Chain Replication for Supporting High Throughput and Availability, Robbert van Renesse, Fred B. Schneider, USENIX Association OSDI '04: 6th Symposium on Peration Systems Design and Implementation.
However, the chain replication technique preliminarily determines nodes to be issuance destinations of the Put request. The problem arises in that the chain replication technique is not able to issue the Put request to an arbitrary node. In view of this, a storage system that distributes installation location of nodes does not equally execute processings in response to Put requests issued by a plurality of clients.
FIG. 22 is a block diagram illustrating a timing at which a received Put request is processed. In an example in FIG. 22, a client 8a and a first node are installed in a data center #1 while a client 8b is installed in a data center #2. In the example illustrated in FIG. 22, a Put request issued by the client 8a arrives at the first node 2 msec after being issued due to network delay while a Put request issued by the client 8b arrives at the first node 25 msec after being issued due to network delay.
Here, assume that the client 8a issued a Put request 10 msec after the client 8b issued a Put request. In this case, the first node receives the Put request issued by the client 8a in first as illustrated by (E) in FIG. 22. Then, the first node receives the Put request issued by the client 8b as illustrated by (F) in FIG. 22. In view of this, the first node executes the Put request later issued by the client 8a before the Put request earlier issued by the client 8b. 